1. Field of the Invention
The present invention relates generally to a vector quantization method, and in particular, to a method of rapidly searching for an optimum codeword for nearest neighbor vector quantization.
2. Description of the Related Art
Nearest neighbor vector quantization (NNVQ) is a quantization method that is most popularly used in a data compression and recognition field. At a given bit rate, such nearest neighbor vector quantization has less quantization error than scalar quantization such as pulse code modulation (PCM), differential pulse code modulation (DPCM) and adaptive differential pulse code modulation (ADPCM). That is, nearest neighbor vector quantization is popularly applied to the fields of speech coding, audio coding, image coding, and speech recognition.
To perform nearest neighbor vector quantization, an operation of searching for an optimum codeword in searching a codebook comprised of a plurality of codewords and quantizing an input vector through the search is required. The optimum codeword refers to a codeword where a quantization error with the input vector is minimized. Conventional methods proposed to search for an optimum codeword through the codebook search can be classified into the following three methods. A first method is a vector quantization method by full search, for performing nearest neighbor vector quantization on all codewords constituting a codebook, a second method is a vector quantization method using a partial distance search scheme, and a third method is a vector quantization method using a threshold.
First, a method for performing nearest neighbor vector quantization by full search, which corresponds to the first method, will be described herein below.
FIG. 1 is a flowchart illustrating a procedure for performing nearest neighbor vector quantization by full search. Referring to FIG. 1, parameter values xe2x80x98Dminxe2x80x99, xe2x80x98ixe2x80x99 and xe2x80x98indexxe2x80x99 for nearest neighbor vector quantization are initialized in step 110. That is, the xe2x80x98Dminxe2x80x99 parameter is set to a maximum value xe2x80x98maxxe2x80x99, and the xe2x80x98ixe2x80x99 and the xe2x80x98indexxe2x80x99 parameters are set to 0. xe2x80x98Dminxe2x80x99 is a parameter for setting the minimum value among quantization errors between codewords {overscore (yi)} constituting a codebook and an input vector {overscore (x)}, and xe2x80x98ixe2x80x99 is a parameter for selecting one codeword from the codewords {overscore (yi)} in order to calculate a quantization error with the input vector {overscore (x)}. If it is assumed that the total number of the codewords constituting the codebook is N, then xe2x80x98ixe2x80x99 ranges from 1 to N. The parameter xe2x80x98indexxe2x80x99 means an index indicating a codeword corresponding to the minimum quantization error value Dmin with the input vector {overscore (x)}. Therefore, xe2x80x98indexxe2x80x99 will become a particular value among integers between 1 and N, which is the range of xe2x80x98ixe2x80x99.
If initialization of the parameters is completed, xe2x80x98ixe2x80x99 is compared with xe2x80x98Nxe2x80x99 in step 112 to determine whether quantization error calculation for all the codewords is completed. If it is determined that quantization error calculation for all the codewords is not completed, the procedure proceeds to step 114. The quantization error calculation is a procedure for determining an optimum codeword that minimizes a quantization error. In step 114, xe2x80x98ixe2x80x99 is increased by 1 so that a codeword with the next index can be selected. If a codeword with the next index is selected in step 114, a quantization error Di between the selected codeword and the input vector is calculated in step 116. For example, a quantization error Di between an input vector {overscore (x)} with an order k and an ith codeword yi can be calculated by                               d          ⁡                      [                                          x                _                            ,                              y                i                                      ]                          =                              D            i                    =                                                    1                k                            ⁢                              (                                                      x                    _                                    -                                      y                    i                                                  )                            ⁢                                                (                                                            x                      _                                        -                                          y                      i                                                        )                                T                                      =                                          1                k                            ⁢                                                ∑                                      j                    =                    1                                    k                                ⁢                                  xe2x80x83                                ⁢                                                      [                                                                                            x                          j                                                _                                            -                                              y                        ij                                                              ]                                    2                                                                                        (        1        )            
where k means an order of the input vector {overscore (x)}, yi means an ith codeword, and {overscore (xj)} and yij mean jth elements of the vector {overscore (x)} and the codeword yi, respectively.
If calculation of the Di corresponding to the current xe2x80x98ixe2x80x99 is completed in step 116, it is determined in step 118 whether Di is larger than Dmin. If Di is larger than Dmin, the procedure returns to step 112 without changing the Dmin to repeatedly perform the steps 112 to 116. However, if Di is not larger than Dmin, the procedure returns to step 112 after changing the value of Di to the value of Dmin and setting the xe2x80x98indexxe2x80x99 to xe2x80x98ixe2x80x99 in step 120. The reason for setting the value of Di to the value of Dmin is to constantly maintain Dmin as the minimum value, and at this moment, by setting the xe2x80x98ixe2x80x99 to the xe2x80x98indexxe2x80x99, it is possible to designate a corresponding codeword.
The steps 114 to 120 are repeatedly performed until it is determined that the process of determining an optimum codeword for nearest neighbor vector quantization for all of N codewords in step 112 is completed. If the process of determining an optimum codeword for nearest neighbor vector quantization for all of N codewords is completed, Dmin has a minimum quantization error value and the parameter xe2x80x98indexxe2x80x99 will designate a codeword corresponding thereto. Therefore, in step 122, a value set to xe2x80x98indexxe2x80x99 is designated as xe2x80x98best_indexxe2x80x99, and the input vector {overscore (x)} is quantized by a codeword yindex corresponding to the best_index.
In the first method stated above, a quantization error Di with an input vector is calculated for each of all codewords constituting a codebook. The first method has two fundamental problems. First, as an order k of the input vector is increased, complexity of operation needed for the codebook search is increased by geometric progression. Such a problem must be resolved first of all in order to perform nearest neighbor vector quantization on a real-time basis. Second, as an order k of the input vector is increased, a size of a memory required for storing codewords is increased by geometric progression.
For example, assuming that an order of a vector is k and a size of a codebook is N, if the full search scheme is applied, (kxc3x97N) multiplications and (2kxc3x97Nxe2x88x92N) additions, subtractions and comparisons are required in order to quantize an input vector. In the full search scheme, a memory for storing a codebook, a size of the memory being proportional to a size of the codebook, is increased in size by geometric progression as an order k of a vector is increased.
Next, a vector quantization method using a partial distance search (PDS) scheme, which corresponds to the second method, will be described herein below. The vector quantization method using the partial distance search scheme was proposed in IEEE, vol. COM-33, pp. 1132-1133 in order to reduce the number of calculations required in the full search scheme. The entire content of this IEEE document is incorporated herein by reference. When calculating a quantization error between an input vector and each candidate codeword, the second method proposed in IEEE vol. COM-33, pp. 1132-1133 calculates the quantization error for r elements rather than all elements of a candidate vector (where rxe2x89xa6k). This is because while a quantization error for a particular codeword among a plurality of codewords is being calculated, if the quantization error is larger than a minimum quantization error value Dmin from a particular point r to a previous point, it is obvious that even though the quantization error for the particular codeword is calculated further, the quantization error will be larger than Dmin.
FIG. 2 is a flowchart illustrating a vector quantization procedure using the partial distance search scheme. Referring to FIG. 2, parameter values xe2x80x98Dminxe2x80x99, xe2x80x98ixe2x80x99 and xe2x80x98indexxe2x80x99 for nearest neighbor vector quantization are initialized in step 210. That is, xe2x80x98Dminxe2x80x99 is set to a maximum value xe2x80x98maxxe2x80x99, and xe2x80x98ixe2x80x99 and xe2x80x98indexxe2x80x99 are set to 0. If initialization of the parameters is completed, a parameter xe2x80x98rxe2x80x99 for counting the number of elements yi used during quantization error calculation for a particular codeword yi is set to 0 in step 212. The xe2x80x98ixe2x80x99 is compared with the xe2x80x98Nxe2x80x99 in step 214 to determine whether quantization error calculation for all the codewords is completed. If it is determined that quantization error calculation for all the codewords is not completed, the procedure proceeds to step 216. Otherwise, the procedure proceeds to step 228. In step 216, the value of xe2x80x98ixe2x80x99 is increased by 1 so that a codeword with the next index can be selected. If a codeword with the next index is selected in step 216, the value of xe2x80x98rxe2x80x99 is increased by 1 in step 218 so that the next element among elements of a corresponding codeword can be selected. If xe2x80x98ixe2x80x99 and xe2x80x98rxe2x80x99 are determined, a quantization error Dr between an input vector and an element selected by the value of r is calculated beginning at the first element of the selected codeword in step 220. For example, a quantization error Dr between an input vector {overscore (x)} with an order k within a range of r and an ith codeword yi can be calculated by                               D          r                =                              ∑                          j              =              1                        r                    ⁢                      xe2x80x83                    ⁢                                    [                                                                    x                    j                                    _                                -                                  y                  ij                                            ]                        2                                              (        2        )            
where {overscore (xj)} is a jth element of an input vector {overscore (x)}, and yij means a jth element of an ith codeword.
If calculation of Dr corresponding to an rth element of a particular codeword yi is completed by step 220, it is determined in step 222 whether Dr is larger than Dmin. Dmin can become the minimum value among quantization errors calculated by all codewords up to a previous codeword yixe2x88x921. If Dr is larger than Dmin, the procedure proceeds to step 212 without changing the value of Dmin. This is to stop quantization error calculation for the particular codeword yi and then perform quantization error calculation on the next codeword yi+1. However, if Dr is not larger than Dmin in step 222, it is determined in step 224 whether the value of r is identical to an order k of the particular codeword yi (r=k). That is, it is determined whether Dr is a quantization error value calculated for all elements constituting the particular codeword yi. If it is determined in step 224 that quantization error calculation for all elements is not completed (i.e., the value of r is not equal to the value of k), the procedure returns to step 218. Otherwise, the procedure proceeds to step 226. Returning to step 218 is to consider up to the next element including an element for which quantization error calculation has been performed up to now, among the elements constituting the particular codeword yi, for quantization error calculation. Thereafter, calculation of the quantization error Dr is performed through step 220. As described above, the quantization error calculation process for the particular codeword yi is repeatedly performed until the quantization error value Dr calculated for all the elements constituting the particular codeword yi becomes larger than the Dmin.
However, if the value of r is identical to the value of k in step 224, the value of Dr is changed to the value of Dmin and the value of xe2x80x98indexxe2x80x99 is set to xe2x80x98ixe2x80x99 in step 226. Thereafter, the procedure returns to step 212 to perform a quantization error calculation process on the next codeword. Setting the value of Dr to the value of Dmin is to constantly maintain Dmin as the minimum value. At this moment, by setting the value of xe2x80x98ixe2x80x99 to the value of xe2x80x98indexxe2x80x99, it is possible to designate a corresponding codeword. That is, the reason for setting the value of Dr to the value of Dmin in step 226 is because since it was determined in step 222 that Dr was not larger than Dmin, it can be determined that the quantization error value calculated by all elements constituting the yi is the minimum value among the quantization error values calculated up to the present.
Meanwhile, the steps 212 to 226 are repeatedly performed until it is determined that the process of determining an optimum codeword for nearest neighbor vector quantization for all of N codewords in step 214 is completed. If the process of determining an optimum codeword for nearest neighbor vector quantization for all the codewords is completed, Dmin has a minimum quantization error value and xe2x80x98indexxe2x80x99 will designate a codeword corresponding thereto. Therefore, in step 228, a value set to xe2x80x98indexxe2x80x99 is designated as xe2x80x98best_indexxe2x80x99, and the input vector {overscore (x)} is quantized by a codeword yindex corresponding to the best_index.
Compared with the first method, the second method can remarkably reduce the number of multiplications, but needs additional comparison operations undesirably.
A vector quantization method using a threshold, which corresponds to the third method, will now be described herein below. The vector quantization method using a threshold is disclosed in U.S. Pat. No. 5,619,717, issued on Apr. 8, 1997, filed by Erik Staats, the entire contents of which is incorporated herein by reference. The third method reduces the number of calculations by performing nearest neighbor vector quantization using a table in which previously calculated distances between codewords are stored. That is, codewords in a codebook are rearranged on the basis of frequency of quantization or a distance between the codewords, and thresholds associated with the rearranged codewords are separately stored, to thereby perform quantization by a codeword with a threshold corresponding to an input vector.
FIG. 3 is a flowchart illustrating a procedure for performing nearest neighbor vector quantization using a previously calculated distance between codewords. Referring to FIG. 3, codewords in a codebook are rearranged on the basis of quantization frequency or a distance between the codewords in step 310. Thereafter, in step 312, thresholds associated with the rearranged codewords are generated in step 312. For example, if a size of the codebook is N, thresholds associated with other codewords except an Nth codeword are generated. The threshold can be defined as xc2xd of a distance between a corresponding codeword and its nearest codeword. Equation (3) represents a threshold Threshj for a jth codeword yj.
Threshj=0.5xc3x97mink greater than j∥yixe2x88x92yk∥xe2x80x83xe2x80x83(3)
Thresholds calculated in this manner are stored in association with their corresponding codewords. Therefore, for the third method proposed, a separate memory area for storing the thresholds is needed. If generation of the thresholds is completed, an input vector {overscore (x)} is quantized using the rearranged codebook and the stored thresholds in step 314. If a distance between an input vector {overscore (x)} and a codeword yj is smaller than a threshold Threshj corresponding to the codeword yj, a process of searching for the nearest codeword is ended. Then, the input vector {overscore (x)} is quantized by a codeword yj.
The third method must additionally secure a memory space for storing previously calculated distances between codewords, in addition to a memory space for storing the codewords. Thus, compared with the other conventional vector quantization methods, the third method is undesirable since it requires more memory space.
It is, therefore, an object of the present invention to provide a vector quantization method capable of reducing a search range of codewords constituting a codebook which is an object of full search.
It is another object of the present invention to provide a vector quantization method for searching a codebook with a small number of calculations without performance deterioration.
It is further another object of the present invention to provide a method for searching a codebook with a small number of calculations without an additional increase in memory space.
To achieve the above and other objects, there is provided a method for searching a codebook having a plurality of codewords for an optimum codeword for quantizing an input vector. The method comprises the steps of: calculating a lower boundary value and an upper boundary value by subtracting and adding a predetermined threshold from/to an element value corresponding to a particular position among a plurality of elements constituting the input vector; designating, as search object codewords, codewords having element values existing between the lower boundary value and the upper boundary value among element values corresponding to the particular position in the respective codewords constituting the codebook; and determining optimum codewords having a minimum quantization error value through full search for calculating a quantization error value with the input vector for the search object codewords.
Preferably, the step of designating search object codewords comprises the steps of: rearranging the codewords in the codebook in descending order by a size of element values corresponding to the particular position in the respective codewords constituting the codebook; determining a point first corresponding to an element value smaller than the upper boundary value as a start point by comparing the upper boundary value with element values corresponding to the particular position in the rearranged codewords; determining a point first corresponding to an element value larger than an element value that is smaller than the lower boundary value as an end point by comparing the lower boundary value with element values corresponding to the particular position in the rearranged codewords; and designating codewords existing between the start point and the end point as the search codewords.
Preferably, the step of designating search object codewords comprises the steps of: rearranging the codewords in the codebook in ascending order by a size of element values corresponding to the particular position in the respective codewords constituting the codebook; determining a point first corresponding to an element value larger than the lower boundary value as a start point by comparing the lower boundary value with element values corresponding to the particular position in the rearranged codewords; determining a point first corresponding to an element value smaller than an element value that is larger than the lower boundary value by comparing the upper boundary value with element values corresponding to the particular position in the rearranged codewords; and designating codewords existing between the start point and the end point as the search codewords.